#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cmath>
#include <cstring>

using namespace std;

class Solution
{
public:
    // s.leng <= 800
    /// @brief
    /// @param base
    /// @param exp must be positive
    /// @param mod
    /// @return
    long long pow(long long base, int exp, long long mod = INT64_MAX)
    {
        long long res = 1;
        for (; exp; exp /= 2)
        {
            if (exp % 2)
                res = res * base % mod;
            base = base * base % mod;
        }
        return res;
    }
    int countKReducibleNumbers(string s, int k)
    {
        // 对 s.leng 及以下进行枚举

        int length = s.size();

        int INF = 0x3f3f3f3f;

        int MOD = 1e9 + 7;
        int MX = length + 1;

        vector<int> fac(MX, 0); // fac[i] = i!

        fac[0] = 1;

        for (int i = 1; i < MX; ++i)
        {
            fac[i] = fac[i - 1] * (long long)i % MOD;
        }

        vector<int> inv_f(MX, 0);
        inv_f[MX - 1] = pow(fac[MX - 1], MOD - 2, MOD);
        for (int i = MX - 1; i > 0; --i)
        {
            inv_f[i - 1] = inv_f[i] * (long long)i % MOD;
        }

        auto combi = [&](int n, int m)
        {
            if (n < m || m < 0 || n < 0)
            {
                return 0;
            }
            return (fac[n] * inv_f[m] % MOD) *
                   inv_f[n - m] % MOD;
        };

        auto permu = [&](int n, int m)
        {
            if (n < m || m < 0 || n < 0)
            {
                return 0;
            }
            return (fac[n] * inv_f[n - m] % MOD);
        };

        auto getNext = [&](int x)
        {
            int n = 0;
            while (x)
            {
                n += (x & 1);
                x >>= 1;
            }
            return n;
        };

        vector<int> nNumList;

        auto getK = [&](int x)
        {
            if (x < 1)
            {
                return INF;
            }
            int cnt = 0;
            while (x > 1)
            {
                int nx = getNext(x);
                ++cnt;
                x = nx;
            }
            return cnt;
        };

        for (int i = 0; i < MX; ++i)
        {
            int kl = getK(i);
            if (kl < k)
            {
                nNumList.push_back(i);
            }
        }

        long long ans = 0;
        int oneCnt = 0;
        for (int i = 0; i < s.size(); ++i)
        {

            char c = s[i];
            int left = s.size() - i - 1;

            if (c == '0')
            {
                continue;
            }

            for (auto num : nNumList)
            {
                ans = (ans + combi(left, num - oneCnt)) % MOD;
            }
            ++oneCnt;
        }

        return ans;
    }
};